package com.xiaoyu.bitOperation;

/**
 * @program: DS_and_A
 * @description: 只出现一次的数字2  --> 简单思路:使用hashmap或者先排序再找只出现一次的数字
 *  给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 *
 * 输入：nums = [0,1,0,1,0,1,99]
 * 输出：99
 *
 * <<      :     左移运算符，num << 1,相当于num乘以2
 *
 * >>      :     右移运算符，num >> 1,相当于num除以2
 *
 * >>>    :     无符号右移，忽略符号位，空位都以0补齐
 *
 * @author: YuWenYi
 * @create: 2021-05-11 14:57
 **/
public class SingleNumber_137 {
    //官方题解:答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
    public static int singleNumber(int[] nums) {
        int res = 0;
        //int类型的数字有32位
        for (int i = 0; i < 32; i++) {
            int total = 0;
            for (int num : nums) {
                //num >> i & 1,用于获取num数字的二进制的第i位的值
                //total,将所有数字的该二进制第i位上的值都加起来
                total += (num >> i & 1);
            }
            if (total % 3 != 0){
                //1<<i将1左移i位,左移1位即*2,左移两位就*2的平方,以此类推
                //res | num 由于是隔位或操作,因此它就是将每一位上的值加起来
                res = res | (1 << i);  //等价于res = res + (int)Math.pow(2, i);
            }
        }
        return res;
    }

/*
    假设数组是[3,3,3,5]
    它们的二进制为:
    0 0 1 1
    0 0 1 1
    0 0 1 1
    0 1 0 1
    将所有数字的对应位数加起来:
    0 1 3 4
    将该值对3取模:
    0 1 0 1 --> 即为答案
    */

    public static void main(String[] args) {
        int[] nums = new int[]{3,3,7,3,7,7,5,5,5,10};
        System.out.println(singleNumber(nums));
    }
}
